import collections


class Solution(object):
    def minJumps(self, arr):
        dist = 0
        n = len(arr)
        if n == 1:
            return 0
        d = collections.defaultdict(set)
        for index, num in enumerate(arr):
            d[num].add(index)
        st = {0}
        already = {0}
        a_search = set()
        while st:
            dist += 1
            next_st = set()
            for node in st:
                for ux in [node - 1, node + 1]:
                    if 0 <= ux < n:
                        if ux not in already:
                            if ux == n - 1:
                                return dist
                            already.add(ux)
                            next_st.add(ux)
                if arr[node] not in a_search:
                    a_search.add(arr[node])
                    for ux in d[arr[node]]:
                        if ux not in already:
                            if ux == n - 1:
                                return dist
                            already.add(ux)
                            next_st.add(ux)
            st = next_st


data = Solution()
arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404]
print(data.minJumps(arr))
